import java.util.ArrayList;
import java.util.Collection;
import java.util.Collections;
import java.util.List;

public class Pruning {
    class Node{
        Node parent;
        int city;
        int d;
        Node(int city,int d,Node parent){
            this.city=city;
            this.d=d;
            this.parent=parent;
        }

        @Override
        public String toString() {
            return ""+city+"-"+d;
        }
    }
    final int N;
    final int start;//出发点
    int[][] D;//用于存储两个城市之间的距离
//    boolean[] done;//用于存储已访问过的城市
    List<Node> queue=new ArrayList<>();//树

    /*
     * 贪心算法解决TSP问题
     * 输入为：距离矩阵，城市个数，出发点。
     */
    public Pruning(int D[][],int N,int start){
//        done = new boolean[N];
        this.start=start;
        this.D=D;
        this.N=N;
    }
    public List<Integer> run(){

        Node root= new Node(start,0,null);
        queue.add(root);
//        done[start]=true;
        for (int deep=1;deep<N;++deep){
            List<Node> queue1=new ArrayList<>();
            for (Node node :queue){
                boolean[] done=getDone(node);
                for (int i=0;i<N;++i){
                    if (node.city==i) continue;//排除自己到自己
                    else if (done[i]) continue;//排除已经走过的
                    queue1.add(new Node(i,node.d+D[node.city][i],node));
                }
                queue1.sort((n1,n2)->n1.d-n2.d);
//                queue1=queue1.subList(0,queue1.size()>N? N-1:queue1.size()-1);//排除后面的
            }
//            System.out.println(queue1);
//            System.out.println(getRes(queue.get(0)));
            queue=queue1.subList(0,queue1.size()>N? N-1:queue1.size()-1);
        }

        return getRes(queue.get(0));
    }

    private List<Integer> getRes(Node node) {
        List<Integer> steps=new ArrayList<>();
        while (node.parent!=null) {
            steps.add(node.city);
            node=node.parent;
        }
        steps.add(node.city);
        Collections.reverse(steps);
        return steps;
    }

    int deep=0;
    void fact(Node root){
//        deep++;
//        if (deep==N)  return;
        boolean[] done=getDone(root);
        List<Node> queue1=new ArrayList<>();
        for (int i=0;i<N;++i){
            if (root.city==i) continue;//排除自己到自己
            else if (done[i]) continue;//排除已经走过的
            queue1.add(new Node(i,root.d+D[root.city][i],root));
        }
        queue1.sort((n1,n2)->n1.d-n2.d);
        queue=queue1.subList(0,N);
        System.out.println(queue);

    }

    private boolean[] getDone(Node root) {
        boolean[] done=new boolean[N];
        while (root.parent!=null) {
            done[root.city] = true;
            root=root.parent;
        }
        done[root.city] = true;
        return done;
    }

    private int getNextStep(int step) {
        return 0;
    }

}
